package com.mayajie.binarytree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树的遍历
 *
 * @author mayajie
 * @date 2021/10/26
 */
public class Order {

    /**
     * 访问当前结点的值
     *
     * @param bt
     */
    public static void visit(LinkedStorage bt) {
        System.out.println(bt.getMiddle());
    }

    /**
     * 先序遍历
     *
     * @param bt
     */
    public static void preOrder(LinkedStorage bt) {
        if (bt != null) {
            visit(bt);
            preOrder(bt.getlChild());
            preOrder(bt.getrChild());
        }
    }

    /**
     * 中序遍历
     *
     * @param bt
     */
    public static void inOrder(LinkedStorage bt) {
        if (bt != null) {
            inOrder(bt.getlChild());
            visit(bt);
            inOrder(bt.getrChild());
        }
    }

    /**
     * 后序遍历
     *
     * @param bt
     */
    public static void postOrder(LinkedStorage bt) {
        if (bt != null) {
            postOrder(bt.getlChild());
            postOrder(bt.getrChild());
            visit(bt);
        }
    }

    /**
     * 求二叉树的高度
     *
     * @param bt
     * @return
     */
    public static int height(LinkedStorage bt) {
        if (bt == null) {
            return 0;
        } else {
            int lh = height(bt.getlChild());
            int rh = height(bt.getrChild());
            return (lh > rh ? lh : rh) + 1;
        }
    }

    /**
     * 层次遍历
     *
     * @param bt
     */
    public static void levelOrder(LinkedStorage bt) {
        if (bt != null) {
            Queue<LinkedStorage> queue = new LinkedList();
            queue.add(bt);
            while (!queue.isEmpty()) {
                LinkedStorage current = queue.poll();
                visit(current);
                if (current.getlChild() != null) {
                    queue.offer(current.getlChild());
                }

                if (current.getrChild() != null) {
                    queue.offer(current.getrChild());
                }
            }
        }
    }

    /**
     * 先序遍历非递归实现
     *
     * @param bt
     */
    public static void preOrderNonRecursive(LinkedStorage bt) {
        if (bt != null) {
            Stack<LinkedStorage> stack = new Stack<>();
            while (bt != null || !stack.isEmpty()) {
                if (bt != null) {
                    visit(bt);
                    stack.push(bt);
                    bt = bt.getlChild();
                } else {
                    LinkedStorage current = stack.pop();
                    bt = current.getrChild();
                }
            }
        }
    }

    /**
     * 中序遍历非递归实现
     *
     * @param bt
     */
    public static void inOrderNonRecursive(LinkedStorage bt) {
        if (bt != null) {
            Stack<LinkedStorage> stack = new Stack<>();
            while (bt != null || !stack.isEmpty()) {
                if (bt != null) {
                    stack.push(bt);
                    bt = bt.getlChild();
                } else {
                    LinkedStorage current = stack.pop();
                    visit(current);
                    bt = current.getrChild();
                }
            }
        }
    }

    /**
     * 后序遍历非递归实现
     *
     * @param bt
     */
    public static void postOrderNonRecursive(LinkedStorage bt) {
        if (bt != null) {
            Stack<LinkedStorage> stack = new Stack<>();
            Stack<Integer> countStack = new Stack<>();
            while (bt != null || !stack.isEmpty()) {
                if (bt != null) {
                    stack.push(bt);
                    countStack.push(0);
                    bt = bt.getlChild();
                } else {
                    Integer count = countStack.peek();
                    if (count == 0) {
                        LinkedStorage parent = stack.peek();
                        bt = parent.getrChild();
                        countStack.push(countStack.pop() + 1);
                    } else if (count == 1) {
                        LinkedStorage parent = stack.pop();
                        visit(parent);
                        countStack.pop();
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        LinkedStorage bt = new LinkedStorage();
        bt.save();
        System.out.println(height(bt)); //3
//        preOrder(bt); //1245367
//        inOrder(bt); //4251637
//        postOrder(bt); //4526731
//        levelOrder(bt); //1234567
//        preOrderNonRecursive(bt);
//        inOrderNonRecursive(bt);
        postOrderNonRecursive(bt);
    }
}
